import type { Node, Edge, Connection } from '@xyflow/react';
import { NodeType, type NodeData } from '../types/behaviorTree';

/**
 * 检查添加新连接后是否会形成循环
 * @param nodes 所有节点
 * @param edges 现有边
 * @param newConnection 新连接
 * @returns 如果会形成循环返回 true，否则返回 false
 */
export function hasCycle(
  nodes: Node<NodeData>[],
  edges: Edge[],
  newConnection: Connection
): boolean {
  // 构建临时的边数组，包含新的连接
  const tempEdges = [
    ...edges,
    {
      id: `temp-${newConnection.source}-${newConnection.target}`,
      source: newConnection.source,
      target: newConnection.target,
      type: 'default' as const,
    },
  ];

  // 构建邻接表
  const adj = new Map<string, string[]>();
  nodes.forEach((node) => adj.set(node.id, []));
  tempEdges.forEach((edge) => {
    const children = adj.get(edge.source);
    if (children) {
      children.push(edge.target);
    }
  });

  // DFS 检测循环
  const visited = new Set<string>();
  const recursionStack = new Set<string>();

  const checkCycleOnTemporaryGraph = (nodeId: string): boolean => {
    visited.add(nodeId);
    recursionStack.add(nodeId);

    const neighbors = adj.get(nodeId) || [];
    for (const neighborId of neighbors) {
      if (!visited.has(neighborId)) {
        if (checkCycleOnTemporaryGraph(neighborId)) {
          return true;
        }
      } else if (recursionStack.has(neighborId)) {
        return true; // 发现循环
      }
    }
    recursionStack.delete(nodeId);
    return false;
  };

  // 检查所有节点（处理多个连通分量的情况）
  for (const node of nodes) {
    if (!visited.has(node.id)) {
      if (checkCycleOnTemporaryGraph(node.id)) {
        return true;
      }
    }
  }

  return false;
}

/**
 * 验证节点连接是否符合行为树规则
 * @param sourceNode 源节点
 * @param targetNode 目标节点
 * @param edges 现有边
 * @returns 验证结果，包含是否有效和失败原因
 */
export function validateNodeConnectionRules(
  sourceNode: Node<NodeData>,
  targetNode: Node<NodeData>,
  edges: Edge[]
): { valid: boolean; reason?: string } {
  // 规则 1: 装饰器节点只能有一个子节点
  if (sourceNode.type === NodeType.Decorator) {
    const children = edges.filter((edge) => edge.source === sourceNode.id);
    if (children.length >= 1) {
      return { valid: false, reason: '装饰器节点只能有一个子节点' };
    }
  }

  // 规则 2: 叶子节点（Action, Condition）不能有子节点
  if (sourceNode.type === NodeType.Action || sourceNode.type === NodeType.Condition) {
    return { valid: false, reason: '动作和条件节点不能有子节点' };
  }

  // 规则 3: 确保目标节点不能已有父节点
  const hasParent = edges.some((edge) => edge.target === targetNode.id);
  if (hasParent) {
    return { valid: false, reason: '目标节点已有父节点' };
  }

  return { valid: true };
}

/**
 * 综合验证连接的有效性
 * @param connection 待验证的连接
 * @param nodes 所有节点
 * @param edges 现有边
 * @returns 验证结果
 */
export function isValidConnection(
  connection: Connection,
  nodes: Node<NodeData>[],
  edges: Edge[]
): { valid: boolean; reason?: string } {
  const sourceNode = nodes.find((node) => node.id === connection.source);
  const targetNode = nodes.find((node) => node.id === connection.target);

  // 检查源节点和目标节点是否存在
  if (!sourceNode || !targetNode) {
    return { valid: false, reason: '源节点或目标节点不存在' };
  }

  // 检查自连接
  if (connection.source === connection.target) {
    return { valid: false, reason: '不能连接到自身' };
  }

  // 检查是否会形成循环
  if (hasCycle(nodes, edges, connection)) {
    return { valid: false, reason: '连接会形成循环' };
  }

  // 验证行为树特定规则
  return validateNodeConnectionRules(sourceNode, targetNode, edges);
}

